#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<string> Permutation(string str) {
	vector<string> seq_v,subSeq_v;
	int ssize = str.size();
	if (ssize == 0)
		return seq_v;
	if (ssize == 1)
	{
		seq_v.push_back(str);
		return seq_v;
	}
	subSeq_v = Permutation(str.substr(1));
	bool isSame = true;
	if (subSeq_v.size() == 1)
	{
		char c = subSeq_v[0][0];
		for(int  i = 1; i < subSeq_v[0].size(); ++i)
			if (c != subSeq_v[0][i])
			{
				isSame = false;
				break;
			}
	}
	if (isSame && str[0] == str[1])
	{
		subSeq_v[0].insert(0, str, 0 ,1);
		return subSeq_v;
	}
	else
	{
		for (int i = 0; i < subSeq_v.size(); ++i)
		{
			string substr = subSeq_v[i];
			string left = substr.insert(0, str, 0, 1);
			substr = subSeq_v[i];
			string right = substr.insert(subSeq_v[i].size(), str, 0, 1);
			seq_v.push_back(left);
			seq_v.push_back(right);
		}
		return seq_v;
	}
}



//int main()
//{
//	string s = "abc";
//	vector<string> v;
//	//v.push_back(s);
//	//s.insert(s.size(), s, 0, 1);
//	////string sc =s[0];
//	//v[0].insert(0, s,0,1);
//	//cout << s << endl;
//	//cout << v[0] << endl;
//	v = Permutation(s);
//
//	for (auto seq : v)
//	{
//		cout << seq << endl;
//	}
//
//	system("pause");
//	return 0;
//}